package com.ag.improvedjava.collections.sort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import com.ag.improvedjava.utils.Requires;

class MergeSort implements Sort {

	@Override
	public <T extends Comparable<? super T>> Collection<T> sort(final Collection<T> collection) {
		Requires.requireNonNull(collection, "The input collection can not be null.");
		
		Object[] array = collection.toArray();
		Object[] temp = new Object[array.length];
		mergeSort(array, temp, 0, array.length - 1);
		
		List<T> result = new ArrayList<>(array.length);
		for (Object o : array) {
			@SuppressWarnings("unchecked")
			T t = (T) o;
			result.add(t);
		}
		return result;
	}
	
	private void mergeSort(Object[] array, Object[] temp, int left, int right) {
		if (right - left < 1) {
			return;
		}
		if (right - left == 1) {
			@SuppressWarnings("unchecked") // Safe cast as the array was 
			// built from a Collection of Comparable<? super T>
			Comparable<Object> leftValue = (Comparable<Object>) array[left];
			if (leftValue.compareTo(array[right]) > 0) {
				swapArrayElements(array, left, right);
			}
		} else {
			int mid = left + (right - left) / 2;
			mergeSort(array, temp, left, mid);
			mergeSort(array, temp, mid + 1, right);
			merge(array, temp, left, mid + 1, right);
		}
	}
	
	@SuppressWarnings("unchecked")
	// Safe cast as the array was built from a Collection of Comparable<? super T>
	private void merge(Object[] array, Object[] temp, int left, int mid, int right) {
		int leftIndex = left;
		int tempIndex = left;
		int rightIndex = mid;

		Comparable<Object> leftElem = (Comparable<Object>) array[leftIndex];
		Object rightElem = array[rightIndex];
		
		while (leftIndex < mid && rightIndex <= right) {
			
			if (leftElem.compareTo(rightElem) > 0) {
				temp[tempIndex++] = rightElem;
				rightIndex++;
				if (rightIndex <= right) {
					rightElem = array[rightIndex];
				} else {
	                // Only the left list is still active. Therefore we can copy the remainder of 
	                // the left list directly to the appropriate place in data, and then copy the 
	                // appropriate portion of tmp back. 
					System.arraycopy(array, leftIndex, array, tempIndex, mid - leftIndex); 
					System.arraycopy(temp, left, array, left, tempIndex - left); 
				}
			} else {
				temp[tempIndex++] = leftElem;
				leftIndex++;
				if (leftIndex < mid) {
					leftElem = (Comparable<Object>) array[leftIndex];
				} else {
					// Only the right list is still active. Therefore tmpCursor must equal rightCursor, 
	                // so there's no point in copying the right list to tmp and back again. Just copy 
	                // the already-sorted bits back into data. 
					System.arraycopy(temp, left, array, left, tempIndex - left); 
				}
			}
		}
		
	}
	
	private void swapArrayElements(Object[] array, int x, int y) {
		if (x == y) return;
		Object elemAtX = array[x];
		array[x] = array[y];
		array[y] = elemAtX;
	}
}
